package com.nuo.laboratory.dataStructure;

import java.util.Stack;

/**
 * 后入先出
 * <p>
 * 求出最小栈-采用双栈解决
 * <p>
 * 使用双栈来解决
 * 一个栈正常push pop 数据
 * 一个最小栈 保持栈顶为上一个栈的最小值
 * <p>
 * <p>
 * MinStack() 初始化堆栈对象。
 * void push(int val) 将元素val推入堆栈。
 * void pop() 删除堆栈顶部的元素。
 * int top() 获取堆栈顶部的元素。
 * int getMin() 获取堆栈中的最小元素。
 *
 * @author LGC
 */
class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    /**
     * 添加元素
     */
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= getMin()) {
            minStack.push(val);
        }
    }

    /**
     * 删除元素
     */
    public void pop() {
        if (stack.isEmpty()) {
            throw new NullPointerException("stack is empty");
        }
        Integer pop = stack.pop();
        if (!minStack.isEmpty()) {
            if (pop.equals(getMin())) {
                minStack.pop();
            }
        }

    }

    /**
     * 获取栈顶元素
     */
    public int top() {
        if (stack.isEmpty()) {
            throw new NullPointerException("stack is empty");
        }
        return stack.peek();
    }

    /**
     * 获取栈最小元素
     */
    public int getMin() {
        if (minStack.isEmpty()) {
            throw new NullPointerException("minStack is empty");
        }
        return stack.peek();
    }
}

/**
 * 有效括号完全匹配
 * (){}[]
 * 如 [{({[]})}]
 * 利用栈的后入先出特性
 */
class KuoHaoPiPeiStack {
    public boolean isValid(String str) {
        Stack<Character> stack = new Stack<>();
        char[] chars = str.toCharArray();
        for (Character c : chars) {
            if (c.equals('(')) {
                stack.push(')');
            } else if (c.equals('[')) {
                stack.push(']');
            } else if (c.equals('{')) {
                stack.push('}');
            } else {
                // 没有左括号相应的右括号栈
                if (stack.isEmpty()) {
                    return false;
                }
                // 顶栈与下一个字符不相等
                Character pop = stack.pop();
                if (!c.equals(pop)) {
                    return false;
                }
            }
        }
        // 最后如果栈为空，说明完全匹配
        return stack.isEmpty();
    }
}

/**
 * 当前温度几天后才有更高的温度(temperature)
 * 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，
 * 其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替
 * 输入: temperatures = [73,71,75,71,69,72,76,73]
 * 输出: [2, 1, 4, 2, 1, 1, 0, 0]
 */
class TempStack {
    public int[] lastTempStack(int[] temp) {
        Stack<Integer> stack = new Stack<>();
        int[] inx = new int[temp.length];
        for (int i = 0; i < temp.length; i++) {
            // 栈不为空，当前值比栈顶的大 移除栈 计算相差几天
            while (!stack.isEmpty() && temp[i] > temp[stack.peek()]) {
                Integer pop = stack.pop();
                inx[pop] = i - pop;
            }
            stack.push(i);
        }
        return inx;
    }
}



